﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace QueuesAndStacks.CanVisitAllRooms
{
    class MainProject
    {
        static void Main(string[] args)
        {
            IList<IList<int>> list = new List<IList<int>>()
            {
                new List<int>{ 1,3},
                new List<int>{ 3,0,1},
                new List<int>{ 2},
                new List<int>{ 0},
            };
            Console.WriteLine(CanVisitAllRooms(list));

            Console.ReadKey();
        }

        /// <summary>
        /// BFS
        /// </summary>
        /// <param name="rooms"></param>
        /// <returns></returns>
        public static bool CanVisitAllRooms(IList<IList<int>> rooms)
        {
            int[] room = new int[rooms.Count];
            Queue<IList<int>> que = new Queue<IList<int>>();
            que.Enqueue(rooms[0]);
            room[0] = 1;
            while (que.Any())
            {
                int size = que.Count;
                for (int i = 0; i < size; i++)
                {
                    IList<int>  list=  que.Dequeue();
                    for (int j = 0; j < list.Count; j++)
                    {
                        if (room[list[j]] ==0)
                        {
                            que.Enqueue(rooms[list[j]]);
                            room[list[j]] = 1;
                        }
                    }
                }
            }
            bool isCan = true;
            foreach (var item in room)
            {
                if (item==0)
                {
                    isCan = false;
                }
            }
            return isCan;
        }
    }
}
